package cn.dglydrpy.study.algorithm.od;

import java.util.*;

/**
 * @author Yyy
 * @date 2024/11/6 11:47
 * @description
 * 题目描述：在某个项目中有多个任务，每个任务有开始时间和截止时间，求可以处理的最大任务数。
 * TODO
 输入：
 3
1 1
1 2
1 3
 输出：
3 
 */
public class Od0012_DealTask {

    public static void main(String[] args) {

        Scanner scanner = new Scanner(System.in);
        while (scanner.hasNextLine()){
            
            int n = Integer.valueOf(scanner.nextLine());
            int[][] tasks = new int[n][2];

            for(int i = 0; i< n ; i++ ){
                String[] s = scanner.nextLine().split(" ");
                tasks[i][0] = Integer.valueOf(s[0]);
                tasks[i][1] = Integer.valueOf(s[1]);
            }
            
            
            int ans = myAnswer(tasks);
            System.out.println(ans);

            int answer1 = answer1(tasks);
            System.out.println(answer1);

            int answer2 = answer2(tasks);
            System.out.println(answer2);
        }
        
        
    }

    private static int myAnswer(int[][] tasks) {
        if(tasks.length < 0){
            return 0;
        }
        
        int ans = 0;
        List<Task> taskList = new ArrayList<>();
        for(int i = 0;i<tasks.length;i++){
            Task task = new Task(tasks[i][0],tasks[i][1]);
            taskList.add(task);
        }

        taskList.sort((o1,o2) ->
            {
                return o1.end == o2.end ? o1.start - o2.start : o1.end - o2.end;
            }
        );
        
        int endTime = -1;
        for (Task task : taskList) {
            if (task.end >= endTime) {
                ans ++;
                endTime = task.end;
            }
        }
        
        return ans;
    }
    
    private static class Task{
        private int start;
        private int end;

        public Task(int start, int end) {
            this.start = start;
            this.end = end;
        }
    }
    
    

    public static int answer1(int[][] tasks) {

        // 使用自定义的比较器对任务数组进行排序，按照截止时间升序排列，如果截止时间相同则按照开始时间升序排列
        Arrays.sort(tasks, new Comparator<int[]>() {
            @Override
            public int compare(int[] t1, int[] t2) {
                int L1 = t1[1] - t1[0] + 1;
                int L2 = t2[1] - t2[0] + 1;
               
                return L1 == L2 ? (t1[0] == t2[0] ? t1[1] - t2[1]:t1[0] - t2[0]) : L1-L2;
            }
        });
        int count = 0;
        // 记录当前已安排任务的最晚截止时间
        int endTime = 0;
        for (int[] task : tasks) {
            // 如果当前任务的开始时间大于等于已安排任务的最晚截止时间，说明可以安排这个任务
            if (task[0] >= endTime) {
                count++;
                endTime = task[1];
            }
        }
        return count;
    }

    public static int answer2(int[][] tasks) {
     
        // 对任务按照结束时间升序排序
        // 冒泡排序实现按照结束时间升序排序任务
        for (int i = 0; i < tasks.length - 1; i++) {
            for (int j = 0; j < tasks.length - i - 1; j++) {
                if (tasks[j][1] > tasks[j + 1][1]) {
                    int[] temp = tasks[j];
                    tasks[j] = tasks[j + 1];
                    tasks[j + 1] = temp;
                }
            }
        }
        
        int count = 0;
        int endTime = 0;
        for (int[] task : tasks) {
            if (task[0] >= endTime) {
                // 如果任务的开始时间晚于等于当前已完成任务的结束时间，
                // 则可以处理这个任务
                count++;
                endTime = task[1];
            }
        }
        return count;
    }

}
